package leetcode; /**
 * description:
 * author:zt
 * date:2021-09-22
 */

/**
 * 给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。
 *
 * 每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
 *
 * 这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
 *
 * 返回一个由上述 k 部分组成的数组。
 */
public class leetcode725 {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int n = 0;
        ListNode tmp = head;
        while (tmp!=null){
            n++;
            tmp = tmp.next;
        }
        int part = n/k , remain = n%k;
        ListNode[] res = new ListNode[k];
        ListNode cur =  head;
        for (int i = 0;i < k && cur != null; i++){
            res[i] = cur;
            int partSize = part + (i < remain? 1: 0);
            for (int j = 1; j < partSize; j++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = null;
            cur = next;
        }
        return res;
    }
}
